package leetcode_acm.backtrack;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月23日 11:38
 */
public class Partition {
    private List<List<String>> res;
    private boolean[][] dp;
    public List<List<String>> partition(String s) {
        if(s == null){
            return Collections.emptyList();
        }
        char[] str = s.toCharArray();
        if(str.length == 0){
            return Collections.emptyList();
        }
        //1.预处理,先处理出来各个位置的回文串的情况
        res = new ArrayList<>();
        dp = getDp(str);
        //2. 开始回溯
        backtrack(str,0,new ArrayList<>());
        return res;
    }
    private boolean[][] getDp(char[] s){
        //定义为闭区间[i,j]上的回文串的情况
        boolean[][] dp = new boolean[s.length][s.length];
        //base-case
        for(int i = 0;i< s.length;i++){
            dp[i][i] = true;
        }
        //开始递推,注意要从下到上,从左到右
        for(int i = s.length-1;i >= 0;i--){
            for(int j = i;j < s.length;j++){
                if(s[i] != s[j]){
                    continue;
                }
                //注意区间的合法性
                //假设[i,j]中含有一个元素,也就是说是[i,i],那么[i+1,j-1]=>[i+1,i-1],这种区间显然不合法
                if(i == j){
                    dp[i][j] = true;
                }
                //1.假设[i,j]中含有两个元素,也就是说是[i,i+1],那么[i+1,j-1]=>[i+1,i],这种区间显然不合法
                if(j - i +1 == 2 && s[i] == s[j]){
                    dp[i][j] = true;
                }
                //2.假设[i,j]中含有三个元以上元素,比如说是[i,i+2],那么[i+1,j-1]=>[i+1,i+1],能确保含有一个元素
                if(j - i +1 > 2 && dp[i+1][j-1]){
                    dp[i][j] = true;
                }
            }
        }
        return dp;
    }
    /*回溯代码的具体逻辑*/
    private void backtrack(char[] s,int startIndex,List<String> path){
        if(startIndex == s.length){
            res.add(new ArrayList<>(path));
            return;
        }
        //然后开始划分子串,判断[startIndex,i]上的元素是否是回文子串
        for(int i = startIndex;i < s.length;i++){
            if(dp[startIndex][i]){
                //做出选择
                path.add(new String(s,startIndex,i-startIndex+1));
                //递归回溯
                backtrack(s,0,path);
                path.remove(path.size()-1);
            }
        }
    }
}
